package psn.zjk.career.interview.algorithm;

/**
 * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
 * 要求时间复杂度为O(n)。
 *
 * @author zhangjk
 * @Description
 * @CREATE_TIME 2021/3/21 21:40
 */
public class LCOffer42 {

    public int maxSubArray(int[] nums) {
        int sum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //用原数组元素i来储存，0-i最大的组合的和
            nums[i] += Math.max(nums[i - 1], 0);
            sum = Math.max(nums[i], sum);
        }
        return sum;
    }

    //==================
//    public int maxSubArray(int[] nums) {
//        if(nums==null||nums.length==0){
//            return 0;
//        }
//        int sum=nums[0];
//        for(int i=1;i<nums.length;i++){
//            sum=Math.max(max(i,nums),sum);
//        }
//        return sum;
//    }
//
//    public int max(int i,int[] nums){
//        if(i==0){
//            return nums[0];
//        }
//        return nums[i]+Math.max(max(i-1,nums),0);
//    }

    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(new LCOffer42().maxSubArray(nums));
    }
}